// 3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

// 给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

 

// 示例：

// 输入: [[4,3,8,4],
//       [9,5,1,9],
//       [2,7,6,2]]
// 输出: 1
// 解释: 
// 下面的子矩阵是一个 3 x 3 的幻方：
// 438
// 951
// 276

// 而这一个不是：
// 384
// 519
// 762

// 总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
// 提示:

// 1 <= grid.length <= 10
// 1 <= grid[0].length <= 10
// 0 <= grid[i][j] <= 15

#include <vector>

using namespace std;

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res{0};
        for (int i{0}; i < m - 2; ++i) {
            for (int j{0}; j < n - 2; ++j) {
                if (grid[i+1][j+1] == 5 && isValid(grid, i, j)) ++res;
            }
        }
        return res;
    }
    bool isValid(vector<vector<int>>& grid, int i, int j) {
        vector<int> nums(10);
        // 确保当前的3*3矩阵中每个数字都是有效的
        for (int x = i; x < i + 2; ++x) {
            for (int y = j; y < j + 2; ++y) {
                int k = grid[x][y];
                if (k < 1 || k > 9 || nums[k] == 1) return false;
                nums[k] = 1; // 这个数字已经出现过
            }
        }
        // 每行每列及对角线的和都是15
        if ((15 != grid[i][j] + grid[i][j+1] + grid[i][j+2]) ||             
            (15 != grid[i+1][j] + grid[i+1][j+1] + grid[i+1][j+2]) ||
            (15 != grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]) ||
            (15 != grid[i][j] + grid[i+1][j] + grid[i+2][j]) ||
            (15 != grid[i][j+1] + grid[i+1][j+1] + grid[i+2][j+1]) ||
            (15 != grid[i][j+2] + grid[i+1][j+2] + grid[i+2][j+2]) ||
            (15 != grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2]) ||
            (15 != grid[i+2][j] + grid[i+1][j+1] + grid[i][j+2]) )
            return false;
        return true;
    }
};